#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

#define MAX_SEQUENCE_LENGTH 100
#define MAX_NUM_SEQUENCES 56

int min(int a, int b, int c) {
    return a < b ? (a < c ? a : c) : (b < c ? b : c);
}

int edit_distance(char* str1, char* str2) {
    int m = strlen(str1);
    int n = strlen(str2);

    int dp[m + 1][n + 1];

    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (i == 0)
                dp[i][j] = j;
            else if (j == 0)
                dp[i][j] = i;
            else if (str1[i - 1] == str2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
        }
    }

    return dp[m][n];
}

int main() {
    FILE* file;
    char line[MAX_SEQUENCE_LENGTH];
    char sequences[MAX_NUM_SEQUENCES][MAX_SEQUENCE_LENGTH];
    int num_sequences = 0;

    // Read sequences from file
    file = fopen("sequences.txt", "r");
    if (file == NULL) {
        perror("Error opening file");
        return 1;
    }

    while (fgets(line, sizeof(line), file) && num_sequences < MAX_NUM_SEQUENCES) {
        line[strcspn(line, "\n")] = 0;  // Remove newline character
        strncpy(sequences[num_sequences], line, sizeof(sequences[num_sequences]) - 1);
        sequences[num_sequences][sizeof(sequences[num_sequences]) - 1] = '\0'; // Ensure null-terminated
        num_sequences++;
    }

    fclose(file);

    // Calculate edit distance and record time
    struct timeval start, end;
    gettimeofday(&start, NULL);

    for (int i = 0; i < num_sequences; ++i) {
        for (int j = i + 1; j < num_sequences; ++j) {
            int distance = edit_distance(sequences[i], sequences[j]);
            printf("Edit distance between sequence %d and sequence %d: %d\n", i + 1, j + 1, distance);
        }
    }

    gettimeofday(&end, NULL);

    double elapsed_time = (end.tv_sec - start.tv_sec) + (end.tv_usec - start.tv_usec) / 1e6;
    printf("Time taken: %f seconds\n", elapsed_time);

    return 0;
}
